Búsqueda de línea híbrida¶
Condiciones de terminación¶
\begin{equation} \| \nabla f(x_k)\|_2 < 10^{-8} \\ \| p_k \|_2 < 10^{-4}\\ \| x_{k-1}-x_k\|_2 < 10^{-5} \|x_{k-1}\|_2 \\ n_{iter}> 249 \end{equation}
Pruebas¶
Rosenbrock¶
In [21]:
resn, pathn = busqueda_linea(rosen, np.array([2,2]), direction='newton')
resm, pathm = busqueda_linea(rosen, np.array([2,2]), direction='max')
plot_path(0, 3, -2, 5, lambda x,y: 100*(y-x**2)**2+(x-1)**2, [1,1], pathn, pathm)
Converge bien en Newton (16 iteraciones) pero no en máximo descenso:
In [22]:
comparar(rosen, [2,2], 'newton', 0)
In [23]:
comparar(rosen, [2,2], 'max', 0)
Rastrigin¶
In [24]:
resn, pathn = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -4, 4, lambda x,y: 20+x**2+y**2-10*np.cos(2*np.pi*x)-10*np.cos(2*np.pi*y), [0,0], pathn, pathm)
Se va a mínimos locales en ambos casos, pero igual es mejor el de máximo descenso.
In [25]:
comparar(rastrigin, [0.4, 0.3], 'max', 0)
In [26]:
comparar(rastrigin, [0.4, 0.3], 'newton', 0)
Griewank¶
In [27]:
resn, pathn = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -1, 1, lambda x,y: (x**2+y**2)/4000-np.cos(x)-np.cos(y/np.sqrt(2))+1, [0,0], pathn, pathm)
No converge al mínimo global.
In [28]:
comparar(griewank, [2,0], 'newton', 0)
In [29]:
comparar(griewank, [2,0], 'max', 0)
Ackley¶
In [30]:
resm, pathm = busqueda_linea(ackley, np.array([0, 1.5]), direction='max')
resn, pathn = busqueda_linea(ackley, np.array([0, 1.5]), direction='newton')
ack = lambda x,y: -20*np.exp(-0.2/2*(x**2+y**2))-np.exp(1/2*(np.cos(2*np.pi*x))+np.cos(2*np.pi*y))+20+np.exp(1)
plot_path(-1, 1, -2, 2, ack, [0,0], pathn, pathm)
Converge en máximo descenso pero no en Newton.
In [31]:
comparar(ackley, [0, 1.5], 'max', 0)
In [32]:
comparar(ackley, [0, 1.5], 'newton', 0)
Branin¶
In [33]:
resn, pathn = busqueda_linea(branin, np.array([-4, 13]), direction='newton')
resm, pathm = busqueda_linea(branin, np.array([-4, 13]), direction='max')
bran = lambda x,y: (y-(5.1/(4*np.pi**2))*x**2+(5/np.pi)*x-6)**2 + 10*(1-(1/(8*np.pi)))*np.cos(x)+10
plot_path(-5, 5, 10, 15, bran, [-np.pi,12.275], pathn, pathm)
Converge al mínimo global en 62 iteraciones con máximo descenso y en 4 con Newton.
In [34]:
comparar(branin, [-4, 13], 'newton', 0.39789)
In [35]:
comparar(branin, [-4, 13], 'max', 0.39789)
Easom¶
In [36]:
resn, pathn = busqueda_linea(easom, np.array([5, 5]), direction='newton')
resm, pathm = busqueda_linea(easom, np.array([5, 5]), direction='max')
eas = lambda x,y: -np.cos(x)*np.cos(y)*np.exp(-(x-np.pi)**2-(y-np.pi)**2)
plot_path(2, 6, 2, 6, eas, [np.pi,np.pi], pathn, pathm)
En ambos casos se atora y casi no avanza.
In [37]:
comparar(easom, [5,5], 'max', -1)
In [38]:
comparar(easom, [5,5], 'newton', -1)
Segunda función de schaffer (2)¶
In [39]:
resn, pathn = busqueda_linea(second_schaffer, np.array([1, 1]), direction='newton')
resm, pathm = busqueda_linea(second_schaffer, np.array([1, 1]), direction='max')
sha2 = lambda x,y: 0.5 + (np.sin(x**2-y**2)**2-0.5)/(1+0.001*(x**2+y**2))**2
plot_path(-2, 2, -2, 2, sha2, [0,0], pathn, pathm)
Newton converge rápido (en 2 iteraciones) y máximo no converge.
In [40]:
comparar(second_schaffer, [1,1], 'newton', 0)
In [41]:
comparar(second_schaffer, [1,1], 'max', 0)
Shubert¶
In [42]:
resn, pathn = busqueda_linea(shubert, np.array([3, 1]), direction='newton')
resm, pathm = busqueda_linea(shubert, np.array([3, 1]), direction='max')
def shub(x,y):
resx = resy = 0
for i in range(1,6):
resx += i*np.cos((i+1)*x+i)
resy += i*np.cos((i+1)*y+i)
return resx*resy
plot_path(0, 45, 0, 6, shub, [36.27,5.48], pathn, pathm)
En máximo descenso converge al mínimo global, en Newton a un local.
In [43]:
comparar(shubert, [1,2], 'max', -186.7309)
In [44]:
comparar(shubert, [1,2], 'newton', -186.7309)